package com.lz.learning;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Qujian {

    public static void main(String[] args) {
        Qujian qujian = new Qujian();
        Pair<Integer, Integer> p1 = new Pair<>(1, 3);
        Pair<Integer, Integer> p2 = new Pair<>(2, 6);
        Pair<Integer, Integer> p3 = new Pair<>(8, 10);
        // qujian.merge(new int[][]{{2, 6}, {8, 10}, {1, 3}});
        qujian.merge(new int[][]{{2, 6}, {6, 10}});
    }

    /**
     * 合并重叠区间
     *
     * @param array
     * @return
     */
    public int[][] merge(int[][] array) {
        if (array.length < 1)
            return new int[0][0];

        Arrays.sort(array, (a, b) -> {
                    if (a[0] > b[0]) return 1;
                    else if (a[0] == b[0]) return 0;
                    else return -1;
                }

        );

        List<int[]> list = new ArrayList<>();

        int[] x = new int[2];
        x[0] = array[1][0];
        x[1] = array[1][1];

        int last = array[1][1];

        for (int i = 1; i < array.length; i++) {

            if (array[i][0] >= x[0] && array[i][0] <= last) {
                //last = Math.max(array[i][1], last);
                if (last < array[i][1]) {
                    last = array[i][1];
                }
            } else {

                x[1] = last;
                list.add(x);

                x = new int[2];
                x[0] = array[i][0];
                x[1] = array[i][1];
                last = array[i][1];
            }

        }
        // z最后一个还在外卖呢
        x[1] = last;
        list.add(x);

        int[][] y = new int[list.size()][2];
        list.toArray(y);
        // System.out.println(x1);
        return y;
    }

    /**
     * 986. 区间列表的交集
     * @param A
     * @param B
     * @return
     */
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        if (A.length < 1 || B.length < 1)
            return new int[0][0];

        // Arrays.sort(A, (a, b) -> {
        //             if (a[0] > b[0]) return 1;
        //             else if (a[0] == b[0]) return 0;
        //             else return -1;
        //         }
        //
        // );

        List<int[]> list = new ArrayList<>();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            int[] a = A[i];
            int[] b = B[j];

            if (a[1] >= b[0] && b[1] >= a[0]) {
                int max = a[0] > b[0] ? a[0] : b[0];
                int min = a[1] < b[1] ? a[1] : b[1];
                list.add(new int[]{max, min});
            }
            if (a[1] < b[1]) i++;
            else j++;
        }

        int[][] y = new int[list.size()][2];
        list.toArray(y);
        // System.out.println(x1);
        return y;
    }

}
